﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

public class ImageDithering
{
    public int count(string dithered, string[] screen)
    {
        int ret = 0;
        char[] fArray = dithered.ToArray();
        foreach (string s in screen)
        {
            foreach (char c in s.ToArray())
            {
                if (fArray.Contains(c)) ret++;
            }
        }

        return ret;
    }
}


public class EmoticonsDiv2
{
    public bool[] calc(int[] v, int[] w, int W)
    {
        int i, j;
        int n = v.Length;   // Number of distinct items (n)

        int[,] m = new int[n + 1, W + 1];

        for (j = 0; j <= W; j++)
            m[0, j] = 0;

        for (i = 1; i <= n; i++)
        {
            for (j = 0; j <= W; j++)
            {
                if (w[i - 1] <= j)
                {
                    m[i, j] = Math.Max(m[i - 1, j], m[i - 1, j - w[i - 1]] + v[i - 1]);
                }
                else
                {
                    m[i, j] = m[i - 1, j];
                }
            }
        }

        bool[] mark = new bool[n];

        i = n;
        j = W;
        while (i > 0 && j > 0)
        {
            if (m[i, j] != m[i - 1, j])
            {
                mark[i - 1] = true;
                j = j - w[i - 1];
                i = i - 1;
            }
            else
            {
                i = i - 1;
            }
        }
        return mark;
    }
}


public class ElephantDrinkingEasy
{
    public int maxElephants(string[] map)
    {
        int n = map.Length;
        bool[,] water = new bool[n, n];
        for (int i = 0; i < n; i++)
        {
            string line = map[i];
            for (int j = 0; j < n; j++)
            {
                if (line[j] == 'Y')
                {
                    water[i, j] = true;
                }
            }
        }

        List<bool[,]> occupyMap = new List<bool[,]>();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!water[i, j]) continue;

                bool[,] m = new bool[n, n];
                for (int ei = 0; ei <= i; ei++)
                {
                    m[ei, j] = true;
                }
                occupyMap.Add(m);

                m = new bool[n, n];
                for (int ei = n - 1; ei >= i; ei--)
                {
                    m[ei, j] = true;
                }
                occupyMap.Add(m);

                m = new bool[n, n];
                for (int ej = 0; ej <= j; ej++)
                {
                    m[i, ej] = true;
                }
                occupyMap.Add(m);

                m = new bool[n, n];
                for (int ej = n - 1; ej >= j; ej--)
                {
                    m[i, ej] = true;
                }
                occupyMap.Add(m);
            }
        }

        int max = 0;
        List<IEnumerable<bool[,]>> result = GetPowerSet(occupyMap).ToList();
        foreach (var mList in result)
        {
            bool found = true;
            bool[,] occupy = new bool[n, n];
            foreach (bool[,] eachM in mList)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (!eachM[i, j]) continue;
                        if (occupy[i, j])
                        {
                            found = false;
                            break;
                        }
                        occupy[i, j] = true;
                    }
                    if (!found) break;
                }
            }

            if (found)
            {
                if (max < mList.Count()) max = mList.Count();
            }
        }
        return max;
    }

    public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
    {
        return from m in Enumerable.Range(0, 1 << list.Count)
               select
                 from i in Enumerable.Range(0, list.Count)
                 where (m & (1 << i)) != 0
                 select list[i];
    }

}

public class LeftAndRightHandedDiv2
{
    public int count(string S)
    {
        int cnt = Regex.Matches(S, "RL").Count;
        return cnt;
    }
}


public class WolvesAndSheep
{
    public int getmin(string[] field)
    {
        return 0;
    }
}

public class SpamChecker
{
    public string spamCheck(string judgeLog, int good, int bad)
    {
        int score = 0;
        for (int i = 0; i < judgeLog.Length; i++)
        {
            if (judgeLog[i] == 'o') score += good;
            else if (judgeLog[i] == 'x') score -= bad;

            if (score < 0) return "SPAM";
        }
        return "NOT SPAM";
    }
}
